#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
    double findMedianSortedArrays(vector<int> &nums1, vector<int> &nums2) {
        // Init members
        arr1 = &nums1;
        arr2 = &nums2;

        size1 = nums1.size();
        size2 = nums2.size();

        if (size1 > size2) {
            size2 = int(size1 / 2) * 2 + (size2 & 1);
        } else if (size2 - size1 > 1) {
            size1 = int(size2 / 2) * 2 + (size1 & 1);
        }

        return findCore(0, size1 - 1, 0, size2 - 1);
    }

    double findCore(int l1, int r1, int l2, int r2) {
        int sz1 = r1 - l1 + 1;
        int sz2 = r2 - l2 + 1;

        // Swap array
        if (sz1 > sz2) {
            swap(arr1, arr2);
            swap(size1, size2);

            swap(l1, l2);
            swap(r1, r2);
            swap(sz1, sz2);
        }

        // Total size less than 6
        if (sz1 + sz2 < 6) {
            vector<int> arr3;
            int i = l1;
            int j = l2;
            while (i <= r1 && j <= r2) {
                int x = get1(i), y = get2(j);
                if (x > y) {
                    arr3.push_back(y);
                    j++;
                } else {
                    arr3.push_back(x);
                    i++;
                }
            }
            while (i <= r1) {
                arr3.push_back(get1(i));
                i++;
            }
            while (j <= r2) {
                arr3.push_back(get2(j));
                j++;
            }

            int size = arr3.size();
            if (size & 1) {
                return arr3[size / 2];
            } else {
                return (double(arr3[size / 2 - 1]) + double(arr3[size / 2])) / 2;
            }
        }

        // Recursively reduce region

        int mid1_s = l1 - 1 + (sz1 + 1) / 2;
        int mid1_t = l1 - 1 + sz1 / 2 + 1;

        int mid2_s = l2 - 1 + (sz2 + 1) / 2;
        int mid2_t = l2 - 1 + sz2 / 2 + 1;

        int x = get1(mid1_s);
        int y = get2(mid2_t);

        if (sz1 == sz2) {
            // x x x x
            // y y y y
            if (x < y) {
                return findCore(mid1_s, r1, l2, mid2_t);
            } else {
                return findCore(l1, mid1_s, mid2_t, r2);
            }
        }

        if (sz2 & 1) {
            // x x x x
            // y y y y y
            if (x < y) {
                return findCore(mid1_t, r1, l2, mid2_t);
            } else {
                return findCore(l1, mid1_s, mid2_t, r2);
            }
        } else {
            // x x x
            // y y y y
            if (x < y) {
                return findCore(mid1_s, r1, l2, mid2_t);
            } else {
                return findCore(l1, mid1_s, mid2_s, r2);
            }
        }
    }

    // Expand short array
    int get1(int index) const {
        int half = (size1 - arr1->size()) / 2;
        if (index < half) {
            return INT_MIN;
        } else if (index >= arr1->size() + half) {
            return INT_MAX;
        }
        return arr1->at(index - half);
    }

    int get2(int index) const {
        int half = (size2 - arr2->size()) / 2;
        if (index < half) {
            return INT_MIN;
        } else if (index >= arr2->size() + half) {
            return INT_MAX;
        }
        return arr2->at(index - half);
    }

    int size1, size2;
    vector<int> *arr1, *arr2;
};

int main(int argc, char *argv[]) {
    Solution sl;
    // vector<int> a{2, 3, 4, 5}, b{-1, -2, 1, 7, 8};
    vector<int> a{1}, b{2, 3, 4, 5};
    cout << sl.findMedianSortedArrays(a, b) << endl;
    return 0;
}